package com.java.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序
 *
 * @author 19252
 * @date 2020/7/18
 */
public class QuickSort {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        // int[] array = new int[]{-9, 78, 0, 0, 0, 23, -567, 70};
        int[] array = new int[]{-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        quickSort.sort(array, 0, array.length - 1);
        for (int value : array) {
            System.out.print(value + " ");
        }

        // 效率测试
        Random random = new Random();
        int[] testArray = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            testArray[i] = random.nextInt(8000000);
        }
        System.out.println();
        long millis = System.currentTimeMillis();
        quickSort.sort(testArray,  0, testArray.length - 1);
        millis = System.currentTimeMillis() - millis;
        System.out.println("数据排序所需的时间：" + millis + "毫秒");
    }

    /**
     * 快速排序
     *
     * @param array 需要排序的数组
     */
    public void sort(int[] array, int left, int right) {
        // 左下标
        int l = left;
        // 右下标
        int r = right;
        // pivot 中轴，即分组的界限
        int index = (l + r) / 2;
        int pivot = array[index];
        int temp;
        // 进行while循环将小于pivot的数放到左边，大于pivot的数放在右边
        while (l < r) {
            // 判断分界左边的数是否大于分界值
            while (array[l] < pivot) {
                l++;
            }
            // 判断分界右边的数是否小于分界值
            while (array[r] > pivot) {
                r--;
            }
            // 如果数组中有多个相同的分界值，不交换，左指针向前移动一位
            if (array[l] == array[r] && l < r){
                l++;
            }else {
                // 当满足交换条件，则交换
                temp = array[r];
                array[r] = array[l];
                array[l] = temp;
            }
        }
        // 解决堆栈溢出问题
        // l == r 到达分界值，接下来的分组包含分界值，使它们位移
        if (l == r){
            l -= 1;
            r ++;
        }
        // 判断左边的分组是否只有一个数
        if (left < l) {
            sort(array, left, l);
        }
        // 判断右边的分组是否只有一个数
        if (r < right) {
            sort(array, r, right);
        }
    }
}
